package com.sheng.leetcode.year2022.month07.day09;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @authers liusheng
 * @date 2022/7/9
 *
 * 873. 最长的斐波那契子序列的长度
 *
 * 如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是斐波那契式的：
 *      n >= 3
 *      对于所有i + 2 <= n，都有X_i + X_{i+1} = X_{i+2}
 * 给定一个严格递增的正整数数组形成序列 arr，找到 arr中最长的斐波那契式的子序列的长度。如果一个不存在，返回0 。
 * （回想一下，子序列是从原序列 arr中派生出来的，
 * 它从 arr中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。
 * 例如，[3, 5, 8]是[3, 4, 5, 6, 7, 8]的一个子序列）
 *
 * 示例 1：
 * 输入: arr = [1,2,3,4,5,6,7,8]
 * 输出: 5
 * 解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。
 *
 * 示例2：
 * 输入: arr = [1,3,7,11,12,14,18]
 * 输出: 3
 * 解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。
 *
 * 提示：
 *
 * 3 <= arr.length <= 1000
 * 1 <= arr[i] < arr[i + 1] <= 10^9
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0873 {

    @Test
    public void test01() {
//        int[] arr = {1,2,3,4,5,6,7,8};
//        int[] arr = {1,3,7,11,12,14,18};
        int[] arr = {2,4,7,8,9,10,14,15,18,23,32,50};
        //4,14,18,32,50
        System.out.println(new Solution().lenLongestFibSubseq(arr));
    }

    @Test
    public void test02() {
        long[] arr = new long[100];
        arr[0] = arr[1] = 1;
        for (int i = 2; i < 100; i++) {
            arr[i] = arr[i - 2] + arr[i - 1];
        }
        System.out.println(Arrays.toString(arr));
    }

}
//class Solution {
//    public int lenLongestFibSubseq(int[] arr) {
//        Map<Integer, Integer> map = new HashMap<>();
//        int length = arr.length;
//        int max = 0;
//        for (int i = 0; i < length - 2; i++) {
//            boolean flag = false;
//            //arr[i]为斐波拉契数列的第一个数
//            for (int j = i + 1; j < length - 1; j++) {
//                int count = 2;
//                int x = i;
//                int y = j;
//                int k = j + 1;
//                while (k < length) {
//                    if (map.containsKey(arr[x]) && map.get(arr[x]) == arr[y]) {
//                        flag = true;
//                        break;
//                    }
//                    if (arr[k] == arr[x] + arr[y]) {
//                        map.put(arr[x], arr[y]);
//                        count++;
//                        x = y;
//                        y = k;
//                    }
//                    k++;
//                }
//                if (flag) {
//                    break;
//                }
//                if (count != 2 && max < count) {
//                    max = count;
//                }
//            }
//            if (flag) {
//                continue;
//            }
//        }
//        return max;
//    }
//}

class Solution {
    public int lenLongestFibSubseq(int[] arr) {
        //n：数组长度，ans：返回值，即最长的子串的长度
        int n = arr.length, ans = 0;
        Map<Integer, Integer> map = new HashMap<>();
        //遍历数组，以数组值为key，index作为值
        for (int i = 0; i < n; i++) {
            map.put(arr[i], i);
        }
        int[][] f = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0 && j + 2 > ans; j--) {
                //如果arr[i]大于等于2 * arr[j]代表构不成斐波那契，不用继续往前找了，直接开始新的循环
                if (arr[i] - arr[j] >= arr[j]) {
                    break;
                }
                //以arr[i] - arr[j]作为key，默认值为-1
                int t = map.getOrDefault(arr[i] - arr[j], -1);
                //如果取得的值为-1，说明arr[j]和arr[i]构不成斐波那契
                if (t == -1) {
                    continue;
                }
                //到这一步说明取得的值t为数组中某一位置的元素，而且包含有t，j，i由小到大构成的斐波那契数
                f[i][j] = Math.max(3, f[j][t] + 1);
                ans = Math.max(ans, f[i][j]);
            }
        }
        return ans;
    }
}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/length-of-longest-fibonacci-subsequence/solution/by-ac_oier-beo2/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
